import java.io.*;
import java.util.*;

class Node {

	private ArrayList<Integer> weights;
	private ArrayList<Integer> adjacentLinks;
	private int node_number;

	public int getNode_number() {
		return node_number;
	}

	public void setNode_number(int node_number) {
		this.node_number = node_number;
	}

	public Node(int n) {
		setWeights(new ArrayList<Integer>());
		setAdjacentLinks(new ArrayList<Integer>());
		node_number = n;
	}

	public ArrayList<Integer> getWeights() {
		return weights;
	}

	public void setWeights(ArrayList<Integer> weights) {
		this.weights = weights;
	}

	public ArrayList<Integer> getAdjacentLinks() {
		return adjacentLinks;
	}

	public void setAdjacentLinks(ArrayList<Integer> adjacentLinks) {
		this.adjacentLinks = adjacentLinks;
	}
}

class Dijkstra {
	/* The graph generated for dijkstra's algorithm to be give as an input */
	private ArrayList<Node> graphArrayList;
	/* The hashmap to get the shortest paths from a particular vertex */
	private HashMap<Integer, ArrayList<Integer>> dijkstraPathHashMap;
	private HashMap<Integer, ArrayList<Integer>> dijkstraPathHashMap1;
	/* Arraylist for storing the shortest paths */
	private ArrayList<Integer> dijkstraShortestPath;
	private HashSet<Integer> hashSet;
	private ArrayList<Integer> actualPath;
	/*
	 * Variable br is for reading from the file and interchangeable with br for
	 * reading from console
	 */
	BufferedReader br1, br;
	// BufferedWriter wr;
	/*
	 * Arraylist for maintaining the vertices that have finished processing in
	 * dijkstra's table
	 */
	private ArrayList<Integer> finished_vertices;

	public HashMap<Integer, ArrayList<Integer>> getDijkstraPathHashMap() {
		return dijkstraPathHashMap;
	}

	public void setDijkstraPathHashMap(
			HashMap<Integer, ArrayList<Integer>> dijkstraPathHashMap) {
		this.dijkstraPathHashMap = dijkstraPathHashMap;
	}

	public ArrayList<Integer> getDijkstraShortestPath() {
		return dijkstraShortestPath;
	}

	public void setDijkstraShortestPath(ArrayList<Integer> dijkstraShortestPath) {
		this.dijkstraShortestPath = dijkstraShortestPath;
	}

	public ArrayList<Integer> getFinished_vertices() {
		return finished_vertices;
	}

	public void setFinished_vertices(ArrayList<Integer> finished_vertices) {
		this.finished_vertices = finished_vertices;
	}

	public ArrayList<Double> getDijkstrasTable() {
		return dijkstrasTable;
	}

	public void setDijkstrasTable(ArrayList<Double> dijkstrasTable) {
		this.dijkstrasTable = dijkstrasTable;
	}

	/* Arraylist for displaying the djistra's Answer */
	private ArrayList<Double> dijkstrasTable;

	public Dijkstra() throws Exception {
		/*
		 * Initializing the Graph which will be given as an input to dijkstra's
		 * algorithm
		 */
		graphArrayList = new ArrayList<Node>();

		/* Arraylist for visited vertices */
		finished_vertices = new ArrayList<Integer>();
		/* Creating an arraylist of doubles */
		dijkstrasTable = new ArrayList<Double>();
		/* Initializing Dijkstra's Path */
		dijkstraPathHashMap = new HashMap<Integer, ArrayList<Integer>>();
		dijkstraPathHashMap1 = new HashMap<Integer, ArrayList<Integer>>();
		/* Initializing the hashset to make the station List unique */
		setHashSet(new HashSet<Integer>());
		/*
		 * Initializing the shortest path arraylist dijkstraShortestPath = new
		 * ArrayList<Integer>();
		 */
		actualPath = new ArrayList<Integer>();
	}

	/* The function to create a graph */
	public void createGraph(int node_number) {
		int choice = 1, input = 0;
		Node n = new Node(node_number);
		String str = "";
		try {

			while (choice == 1) {
				// System.out.println("Enter an adjacent node for node "
				// + node_number + " and its corresponding weight");
				str = br.readLine();
				input = Integer.parseInt(str);
				n.getAdjacentLinks().add(input);
				str = br.readLine();
				input = Integer.parseInt(str);
				n.getWeights().add(input);
				// System.out.println("Press 1 to add more links");
				str = br.readLine();
				choice = Integer.parseInt(str);
			}
			this.getGraphArrayList().add(n);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	/* Function to check if the vertex is already in the list or not */
	boolean check(ArrayList<Integer> arr, double d) {
		for (Integer i : arr) {
			if (i == (int) d)
				return true;
		}
		return false;
	}

	void displayGraph() {
		/* Displaying the Graph */
		for (Node node : getGraphArrayList()) {
			System.out.print(node.getNode_number() + ": ");
			for (Integer j : node.getAdjacentLinks())
				System.out.print(j + "  ");
			System.out.print("\n   ");
			for (Integer j : node.getWeights())
				System.out.print(j + " ");
			System.out.print("\n\n");
		}
	}

	/* Code to show dijkstra's table at a particular table */
	void showDijkstraTable() {
		System.out.println("\nDijkstra's Table");
		for (Double i : dijkstrasTable) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public void printFinishedVertices() {
		for (Integer i : finished_vertices)
			System.out.print(i + " ");
		System.out.println();
	}

	void dijkstra_Algorithm(int count, int source) {
		int i = 0, n = 0, input = 0, vertex_number = 0, adjacent_vertex_number = 0, weight = 0;
		double delta = 0, minimum = 0;
		int randomNumber = 0;
		n = count;
		int var = 14;

		// System.out.println("Var = " + var);
		double inf = Double.POSITIVE_INFINITY;

		/* Taking the input for the source vertex */
		try {
			input = source;
			/* Validating the input till a proper value enters */
			while (input < 1 || input > n) {
				input = Integer.parseInt(br.readLine());
			}
		} catch (NumberFormatException e) {
		} catch (Exception e) {
		}
		/*
		 * Writing the code for a station to be accessible by itself i.e 1 will
		 * have adjacent station only as 1
		 */
		ArrayList<Integer> t = new ArrayList<Integer>();
		t.add(input);
		dijkstraPathHashMap.put(input, t);
		/* Initialisation the loop */
		/* For loop to add numbers of all nodes */

		for (i = 1; i <= n; i++) {
			if (i == input)
				dijkstrasTable.add((double) 0);
			else
				dijkstrasTable.add(inf);
		}

		/* Code for Dijkstra */
		/* Assuming the first one is minimum */
		delta = dijkstrasTable.get(0);
//		System.out.println("R value = " + delta);
		/* Function to show the dijkstra's table */
		while (count != 0) {
			if (count == var) {
//				System.out.println("Dijkstra's table");
//				showDijkstraTable();
			}
			/* To find the minimum in all of the vertices */
			for (i = 0; i < dijkstrasTable.size(); i++) {// Double d : nodes) {
				if (check(finished_vertices, i)) {
					continue;
				} else {
					delta = Math.min(delta, dijkstrasTable.get(i));
				}
			}
//			if (count == var)
//				System.out.println("Delta " + delta);
			/* Finding which vertex */
			for (i = 0; i < dijkstrasTable.size(); i++) {
				if (dijkstrasTable.get(i) == delta) {
					/*
					 * Why we are adding 1 because while adding graphs we gave 1
					 * as the starting value in the for loop. So GraphArrayList
					 * is starting from 1 and finishedVertices and dijkstraTable
					 * will start from zeros
					 */

					vertex_number = i + 1;
					if (check(finished_vertices, i))
						continue;
					else
						break;
				}
			}

			/*
			 * Need to go to that vertex number object in the graph which is a
			 * collection of nodes and iterate through it adjacency list
			 */
			/* So got that vertex */
			Node temp_node = null;
			for (Node temp : getGraphArrayList()) {
				if (temp.getNode_number() == vertex_number) {
					temp_node = temp;
					break;
				}
			}

			/* Code to add the new weight to the table */
			for (i = 0; i < temp_node.getAdjacentLinks().size(); i++) {
				/*
				 * if (check(finished_vertices, i)) { // System.out.println(i +
				 * " finished"); continue; } else {
				 */
				/* getting the weight in that object for its adjacent vertex */
				weight = temp_node.getWeights().get(i) + (int) delta;
				/* Getting the vertex number */
				adjacent_vertex_number = temp_node.getAdjacentLinks().get(i);
				if (adjacent_vertex_number > n)
					continue;
				if (check(finished_vertices, adjacent_vertex_number - 1)) {
					// System.out.println(i + " finished");
					continue;
				}
				/* To find the minimum value of earlier and new value */
				minimum = Math.min(
						dijkstrasTable.get(adjacent_vertex_number - 1), weight);
				/*
				 * System.out.println("adjacent_vertex_number - 1 " +
				 * (adjacent_vertex_number - 1) + "Minimum =" + minimum +
				 * " Weight " + weight);
				 */
				if (minimum == weight) {
					if (dijkstraPathHashMap.get(adjacent_vertex_number) == null) {
						ArrayList<Integer> tempList = new ArrayList<Integer>();
						tempList.add(vertex_number);
						dijkstraPathHashMap.put(adjacent_vertex_number,
								tempList);
					} else {
						ArrayList<Integer> templist = dijkstraPathHashMap
								.get(adjacent_vertex_number);
						templist.add(vertex_number);
						dijkstraPathHashMap.put(adjacent_vertex_number,
								templist);
					}
				} else {

				}
				/*
				 * Replace the old value with the new value. Anyways new value
				 * can also be old value
				 */
				dijkstrasTable.set(adjacent_vertex_number - 1, minimum);
			}
			/* Marking the vertices that have finished executing */
			finished_vertices.add(vertex_number - 1);
			/*
			 * for (Integer y : finished_vertices) {
			 * System.out.print("The marked vertices are : " + y); }
			 */
			/*
			 * Code to print the arraylist containing dijkstra's algorithm's
			 * nodes
			 */

			/* Getting a random value to start finding the minimum value */
			randomNumber = ((int) (Math.random() * 9999)) % n;
			/*
			 * Now checking if that already exists or is in the
			 * finished_vertices arraylist
			 */
			while (check(finished_vertices, randomNumber)) {
				randomNumber = ((int) (Math.random() * 9999)) % n;
			}

			delta = dijkstrasTable.get(randomNumber);
			if (count == var) {
//				showDijkstraTable();
			}
			count--;
			@SuppressWarnings("unused")
			String message = "";
			if (count == 1) {
				// System.out.print("\n");
				for (Double d : dijkstrasTable) {
					// System.out.print(d + "\n");
					message += String.valueOf(d) + "\n";
				}
				expandShortestPaths(input);
				return;
			}
			/*Finction to print the finished vertices*/
//			if (count == var)
//				printFinishedVertices();

		}
	}

	public void expandShortestPaths(int input) {
		/* To iterate through every hashmap to get an arraylist */
		for (Integer i : dijkstraPathHashMap.keySet()) {
			/* To iterate through every arraylist */
			for (Integer j : dijkstraPathHashMap.get(i)) {
				if (i == input) {
					dijkstraPathHashMap1.put(i, new ArrayList<Integer>());
					dijkstraPathHashMap1.get(i).add(i);
					continue;
				} else {
					/*
					 * To iterate through every arraylist of that number which
					 * comes in the arraylist
					 */
					for (Integer k : dijkstraPathHashMap.get(j)) {
						if (dijkstraPathHashMap1.get(i) == null) {
							dijkstraPathHashMap1.put(i,
									new ArrayList<Integer>());
							dijkstraPathHashMap1.get(i).add(k);
						} else
							dijkstraPathHashMap1.get(i).add(k);
					}
					dijkstraPathHashMap1.get(i).add(i);
					dijkstraPathHashMap1.get(i).add(j);
				}
			}
		}
		for (Integer i : dijkstraPathHashMap1.keySet()) {
			Set<Integer> set = new HashSet<Integer>(dijkstraPathHashMap1.get(i));
			ArrayList<Integer> temp = new ArrayList<Integer>(set);
			dijkstraPathHashMap1.put(i, temp);
		}
	}

	public void showShortestpath() {
		for (Integer temp : getDijkstraPathHashMap().keySet()) {
			 System.out.print(temp + ": ");
			for (Integer tempVariable : getDijkstraPathHashMap().get(temp)) {
				 System.out.print(tempVariable + " ");
			}
			 System.out.println();
		}
		 System.out.println();
		for (Integer temp : getDijkstraPathHashMap1().keySet()) {
			 System.out.print(temp + ": ");
			for (Integer tempVariable : getDijkstraPathHashMap1().get(temp)) {
				 System.out.print(tempVariable + " ");
			}
			 System.out.println();
		}
	}

	/* Recursively travels through the hashmap to find the shortest path */
	public void shortestPath(int n) {
		if (n == 1) {
			return;
		}
		for (Integer i : dijkstraPathHashMap.get(n)) {
			actualPath.add(i);
			shortestPath(i);
		}
	}

	public ArrayList<Integer> displayPath(Location l, int n) {
		/* Adding the destination station */
		actualPath.add(n);
		/* Following three lines of code remove */
		ArrayList<Integer> stations = new ArrayList<Integer>();
		Set<Integer> set = new HashSet<Integer>(actualPath);
		actualPath = new ArrayList<Integer>(set);
		// Collections.sort(actualPath);

		for (Integer i : actualPath) {
			// System.out.print(i + " ");
		}

		for (Integer i : actualPath) {
			if (l != null) {
				// System.out.print(l.hashMap.get(i) + " ");
				stations.add(l.hashMap.get(i));
			}
		}
		return stations;
	}

	public static void main(String[] args) throws Exception {
		/* variable declaration */
		int source = 0, i = 0, n = 0;

		/* Creating an object of Dijkstra */
		Dijkstra dijkstra = new Dijkstra();
		// System.out.println("Enter the number of vertices");
		/* No of vertices */
		n = Integer.parseInt(dijkstra.br.readLine());

		/* Input the graph nodes */
		for (i = 1; i <= n; i++)
			dijkstra.createGraph(i);

		/* Method call to display graph */
//		 dijkstra.displayGraph();
		/* Message call to dijkstra's Algorithm */
		source = Integer.parseInt(dijkstra.br.readLine());
		dijkstra.dijkstra_Algorithm(n, source);
		/* Printing the Dijkstra's path */
//		 dijkstra.showShortestpath();
		 dijkstra.shortestPath(8);
		 dijkstra.displayPath(null, 8);
	}

	public ArrayList<Node> getGraphArrayList() {
		return graphArrayList;
	}

	public void setGraphArrayList(ArrayList<Node> graphArrayList) {
		this.graphArrayList = graphArrayList;
	}

	public HashMap<Integer, ArrayList<Integer>> getDijkstraPathHashMap1() {
		return dijkstraPathHashMap1;
	}

	public void setDijkstraPathHashMap1(
			HashMap<Integer, ArrayList<Integer>> dijkstraPathHashMap1) {
		this.dijkstraPathHashMap1 = dijkstraPathHashMap1;
	}

	public HashSet<Integer> getHashSet() {
		return hashSet;
	}

	public void setHashSet(HashSet<Integer> hashSet) {
		this.hashSet = hashSet;
	}

}
